AnthonyAAAAA
个人主页
修改帐号
退出

昵称：AnthonyAAAAA

等级：没等级

文章：0

下次自动登录

登录 注册

找回密码

首页 版面收藏夹 版面目录 精华区收藏夹 关注/粉丝

3

·

MDog

六点勺园约么？

凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数

Anniversary

未名BBS 2018明信片册和巨型鼠标垫限量发售

经过前期的准备，北大未名BBS 于18周年站庆之际面向全站网友推出系列纪念品。纪念品图案均为过往优秀日常进站图片，欢迎大家关注。 　　首发时间：2018年06月20日、21日（星期三、四）10:

deliver

新手上路必读

亲爱的朋友： 　　恭喜您已经通过北大未名BBS的身份认证，非常高兴您成为我们共同的大家庭中新的一员，我们将尽我们所能为您提供完善的服务！收到这封信后，退出BBS然后重新登录，就可以成为正式用户，拥有各

deliver

恭喜您完成注册单身份核验

您已经通过北大未名BBS的身份检验，我们认为您的资料已经符合要求，所以让您通过。我们非常的兴奋，又多了一位使用者加入这个大家庭，我们将会尽力为您提供最好的服务，祝愿您在本站愉快。 　　参与版面讨论

查看全部

修改帐号
偏好设置
校内认证
帮助中心 退出

算分2017期中期末考试题 - 信息科学技术学院(EECS)版 - 北大未名BBS

首页 版面目录 一区: 北京大学
信息科学技术学院(EECS)
算分2017期中期末考试题

返回本版

1

/ 1

跳转

算分2017期中期末考试题

[复制链接] 分享：

楼主

doradatong [离线]

哆啦未

2.2浣熊

发帖数：14 原创分：0

关注

<ASCIIArt> 1楼

算分2017期末考试题回忆版（考试时长：2.5h）

1 伪码，输出一个不是最大的随机数（10分）

2 贪心?：区间集合S，如果两个区间有重叠，称两个区间相互支配，求S的最小子集P，S中所有的区间都能被P中的区间支配（15分）

3 动态规划：带权的编辑距离（15分）

4 线性规划：带等号的对偶线性规划（只用写出对偶）（10分）

5 网络流：n个城市，有道路（无向边），求城市1到城市n的k条路线，且路线经过的道路数最少，每个道路只能被一个路线经过，找不到k条路线则输出no（10分）

6 NPC：

（1）有向图的圈覆盖问题，证明可以多项式时间求解（提示：用二部图匹配算法）

（2）证明边数不超过3的圈覆盖是NPC（即是否存在一个圈覆盖，满足每个圈的边数都不超过3）（20分）

7 近似算法：写出求极大匹配的贪心算法，求该算法和最大匹配算法的近似比，找出紧实例（10分）

8 随机算法：在n个元素的数组中查找数x，每次随机选一个数，如果不是x，就从数组中删去，再次查找。x出现的概率是p，求查找次数的期望（10分）

附件是期中考试题拍照版

·
2017_midterm.pdf(1.3MB)

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

最后修改于2017-06-12
17:35:35

·       发表于2017-06-12 17:29:04

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

daokedao [离线]

道可道

2.8一般站友

发帖数：120 原创分：0

关注

<ASCIIArt> 2楼

请问这是哪里的考题，确定是17年EECS课程考试？我在看《算法设计与分析》（第二版），感觉学的和这些有差异

谢谢

doradatong (哆啦未) 在 ta 的帖子中提到：

算分2017期末考试题回忆版（考试时长：2.5h）

1 伪码，输出一个不是最大的随机数（10分）

2 贪心?：区间集合S，如果两个区间有重叠，称两个区间相互支配，求S的最小子集P，S中所有的区间都能被P中的区间支配（15分）

……

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-03-28 17:20:33

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

Lepidoptera [在线]

はすみ(葉純)

1.4原恒星

发帖数：305 原创分：3

关注

<ASCIIArt> 3楼

作为一个考过的人告诉你，这确实是17年算分期末题，无误

daokedao (道可道) 在 ta 的帖子中提到：

请问这是哪里的考题，确定是17年EECS课程考试？我在看《算法设计与分析》（第二版），感觉学的和这些有差异

谢谢

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-03-28 21:10:18

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

out [离线]

angx

3.5扬州炒饭

发帖数：1384 原创分：0

关注

<ASCIIArt> 4楼

北大出的那本的话不会有什么差异的

daokedao (道可道) 在 ta 的帖子中提到：

请问这是哪里的考题，确定是17年EECS课程考试？我在看《算法设计与分析》（第二版），感觉学的和这些有差异

谢谢

签名档

非专业傻逼

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-03-28 23:25:09

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

daokedao [离线]

道可道

2.8一般站友

发帖数：120 原创分：0

关注

<ASCIIArt> 5楼

是清华出版社的： 《算法设计与分析》 （第二版） 屈婉玲，刘田等  这本书吧？

out (song) 在 ta 的帖子中提到：

北大出的那本的话不会有什么差异的

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

最后修改于2018-03-29
08:58:20

·       发表于2018-03-29 08:56:51

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

weilovebvb [离线]

什变月饼|圣埃克絮佩里

3.7巨阙

发帖数：2972 原创分：11

关注

<ASCIIArt> 6楼

哇 感谢学长！正好是要期中了TUT

怕不是很及时的挖坟

doradatong (哆啦未) 在 ta 的帖子中提到：

算分2017期末考试题回忆版（考试时长：2.5h）

1 伪码，输出一个不是最大的随机数（10分）

2 贪心?：区间集合S，如果两个区间有重叠，称两个区间相互支配，求S的最小子集P，S中所有的区间都能被P中的区间支配（15分）

……

签名档

记者：解决勇士，你们用六场还是七场？

利拉德：六场

记者：真的吗？不会是开玩笑吧？

利拉德：是你先开玩笑的

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

最后修改于2018-04-04
11:07:36

·       发表于2018-04-04 11:06:56

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

davy [在线]

=。=

4.0高级站友

发帖数：1695 原创分：0

关注

<ASCIIArt> 7楼

今年这么早期中。。？？

weilovebvb (什变月饼|圣埃克絮佩里) 在 ta 的帖子中提到：

哇 感谢学长！正好是要期中了TUT

怕不是很及时的挖坟

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-04-04 18:07:48

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

weilovebvb [离线]

什变月饼|圣埃克絮佩里

3.7巨阙

发帖数：2972 原创分：11

关注

<ASCIIArt> 8楼

还有两周

davy (=。=) 在 ta 的帖子中提到：

今年这么早期中。。？？

签名档

二号：二号这里是张预言家 查杀四号

四号：二号在说谎 我是预言家 五号是我的金水

五号：这个金水我不认 我是预言家 查杀八号

八号：前面的都是胡闹 我是真正的预言家 二号是好人

…………

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-04-04 23:48:10

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

redhated [离线]

小红帽

3.6扫雷舰

发帖数：784 原创分：0

关注

<ASCIIArt> 9楼

一定把这本书书后题全做了

daokedao (道可道) 在 ta 的帖子中提到：

是清华出版社的： 《算法设计与分析》 （第二版） 屈婉玲，刘田等  这本书吧？

签名档

发自 PKU Helper (Android 2.1.1)

--

真正的人，总会找到他的同伴的。

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-04-05 11:37:36

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

redhated [离线]

小红帽

3.6扫雷舰

发帖数：784 原创分：0

关注

<ASCIIArt> 10楼

我是指为应付考试而言

daokedao (道可道) 在 ta 的帖子中提到：

是清华出版社的： 《算法设计与分析》 （第二版） 屈婉玲，刘田等  这本书吧？

签名档

发自 PKU Helper (Android 2.1.1)

--

我将为人斗争，反对人的敌人，也要反对我自己。

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-04-05 11:38:08

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

davy [在线]

=。=

4.0高级站友

发帖数：1695 原创分：0

关注

<ASCIIArt> 11楼

可你们实验班

redhated (小红帽) 在 ta 的帖子中提到：

一定把这本书书后题全做了

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-04-05 19:55:08

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

keyes [离线]

受火引诱者

3.6龙泉

发帖数：2620 原创分：2

关注

<ASCIIArt> 12楼

警觉.jpg

weilovebvb (什变月饼|圣埃克絮佩里) 在 ta 的帖子中提到：

还有两周

签名档

无论你欲往何方 伊鲁席尔永在月旁

无论你身在何处 伊鲁席尔仍是故乡

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-04-06 19:14:14

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

kkpoker [离线]

耶米

2.6一般站友

发帖数：54 原创分：0

关注

<ASCIIArt> 13楼

隐约感觉那个不是最大……其实是中位数？

去年我好像也写的不是最大。。。。。

doradatong (哆啦未) 在 ta 的帖子中提到：

算分2017期末考试题回忆版（考试时长：2.5h）

1 伪码，输出一个不是最大的随机数（10分）

2 贪心?：区间集合S，如果两个区间有重叠，称两个区间相互支配，求S的最小子集P，S中所有的区间都能被P中的区间支配（15分）

……

签名档

――我々は神の道具ではない。生きている、意志のある存在なのだ。

それでも人智を超えた運命を否定できない瞬間は訪れる。そんな時、君はどう振舞うだろうか？

極限に身を置いて尚、意志と誇りを抱き続ける姿は美しい。

私はそのような存在になりたいと願ったし、数十年を経た今となっても、"彼女”に畏敬の念を禁じ得ないのである。

——アドル・クリスティン著　『ゲーテ海案内記』序文より

回帖

收起

回信

转载

转寄

收入文集

o单帖

o同主题

发表于2018-06-08 13:17:04

快速回帖

切换到完整模式

签名档

无

·       无

无

匿名

收起 发布(Ctrl+回车)

返回本版

1

/ 1

跳转

快速回复楼主

标题

建议：≤ 24个字

切换到完整模式

签名档

无

·       无

无

匿名

发布(Ctrl+回车)

您输入的密码有误，请重新输入

确认

常用网站 - 相关下载
- 未名站刊
- 关于我们
- 联系我们
- 加入我们
- 帮助中心
- 意见反馈

© 2000–2018 北大未名BBS

 消息

新建聊天





载入中...

搜索

复制